package com.github.hgkmail.hello.leetcode101.pointer.linkedlist;

import com.github.hgkmail.hello.leetcode101.base.CommonUtil;
import com.github.hgkmail.hello.leetcode101.base.ListNode;

public class LC148SortList {
    //链表归并排序
    public ListNode mergeSort(ListNode head) {
        //end case
        if (head==null || head.next==null) {
            return head;
        }
        //divide
        ListNode fast=head, slow=head;
        while (fast.next!=null && fast.next.next!=null) { //必须是有效步数
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode mid = slow.next;
        slow.next=null;
        head=mergeSort(head);
        mid=mergeSort(mid);
        //conquer
        ListNode dummyHead=new ListNode(0);
        ListNode i=head, j=mid, k=dummyHead;
        while (i!=null && j!=null) {
            if (i.val<=j.val) {
                k.next=i;
                i=i.next;
            } else {
                k.next=j;
                j=j.next;
            }
            k=k.next;
        }
        k.next=i!=null?i:j;
        return dummyHead.next;
    }
    public ListNode sortList(ListNode head) {
        //链表归并排序
        return mergeSort(head);
    }

    public static void main(String[] args) {
        ListNode a=new ListNode(3, null);
        ListNode b=new ListNode(1, a);
        ListNode c=new ListNode(2, b);
        ListNode d=new ListNode(4, c);
        CommonUtil.printLinkedList(new LC148SortList().sortList(d));
    }
}
